/*
	约瑟夫问题：n个人围成一个圈，首先第一个人从1
	开始，一个人一个人顺时针报数，报到第m个人，令其出列，
	再从下一个人开始继续报数，直到剩下一个人，即为优胜者
	
	用不带表头结点的循环链表来组织
*/


/* 1.人数必须大于1
   2.不能带有头结点，而是需要头指针
   3.需要循环链表长度以及报数的数字
   4.
 */

#include<stdio.h>
void Josephus1(LNode head,int n,int m)
{
	LNode *p,*q;
	int count = 1;
	int k;
	p = head;

	while (k > 1)
	{
		if (count == m - 1)
		{
			q = p -> next;
			p -> next = q -> next;
			free(q);
			count = 0;
			k--;
		}
		else
		{
			count++;
			p = p -> next;
		}
	}

	if (k == 1)
		printf("the winner is %d\n", p -> data);
	else if (k < 1)
		printf("ERROR\n");
}

void Josephus2(LNode head,int n,int m)
{
	LNode *p,*q;
	int i;
	int j;

	for (i = 1;i < n; i++)
	{
		for (j = 1;j < m;j++)
		{
			q = p
			p  = p -> next;
		}

		q -> next = p -> next;
		free(p);
		p = q -> next;

	}
}